#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 101. 对称二叉树.py
@time: 2022/1/27 13:25
@desc: https://leetcode-cn.com/problems/symmetric-tree/
> 给你一个二叉树的根节点 root ， 检查它是否轴对称。

@解题思路：
    1. 层序遍历：如果对称，每一层的数值都是对称的，按照这个特点每层都对比
    2. 递归：Ot(n), Os(n)
'''

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root: return True
        # 层序遍历
        queue = []
        queue.append([root])
        # 检查每一层的数组是否对称
        while queue:
            level = queue.pop()
            tmp = [] # 记录下一层元素的层序排列
            tmp2 = [] # 记录下一层元素的层序排列的数值，如果有空节点，就存入负无穷
            # 把该层的下一层节点存起来
            while level:
                node = level.pop()
                if node.left: tmp.append(node.left); tmp2.append(node.left.val)
                else: tmp2.append(-2**31)
                if node.right: tmp.append(node.right); tmp2.append(node.right.val)
                else: tmp2.append(-2**31)
            # 检查下一层是否对称
            if tmp:
                n = len(tmp2)
                for i in range(n):
                    if not tmp2[i]== tmp2[n-1-i]: return False
                queue.append(tmp)
        return True

# 递归
class Solution02(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def check(p, q):
            if not p and not q: return True
            if not p or not q: return False
            return p.val==q.val and check(p.left, q.right) and check(p.right, q.left)
        return check(root, root)